package sort;

import java.util.Stack;

public class QuickSortNoReduce {
    public static void main(String[] args) {
        int[] a = {1, 2, 2, 3, 2, 5, 4, 8};
        sort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    private static void sort(int[] a, int low, int high) {
        Stack<Integer> stack = new Stack<>();
        stack.push(low);
        stack.push(high);
        while (!stack.isEmpty()) {
            int h = stack.pop();
            int l = stack.pop();
            int p = partition(a, l, h);
            if (l < p - 1) {
                stack.push(l);
                stack.push(h - 1);
            }
            if (h > p + 1) {
                stack.push(p + 1);
                stack.push(h);
            }
        }
    }

    private static int partition(int[] a, int low, int high) {
        int povit = a[low];
        int i = low;
        while (low < high) {
            while (low < high && povit >= a[low + 1]) {
                low++;
            }
            while (low < high && povit <= a[high]) {
                high--;
            }
            if (a[low] > a[high]) {
                int temp = a[low];
                a[low] = a[high];
                a[high] = temp;
            }
        }
        a[i] = a[low];
        a[low] = povit;
        return low;
    }
}
